1. Technical Field
The present invention generally relates to a method and apparatus for low-density parity-check (LDPC) encoding of data and particularly relates to block encoding of data based on a parity check matrix for mapping the data into LDPC code words for binary and multilevel modulation for data communication and for recording systems.
2. Description of Related Art
In Gallager: “Low-density parity-check codes, Cambridge, Mass. MIT Press 1963.”, it is shown that, based on message-passing decoders, it is possible to come extremely close to the channel capacity of the binary-input additive white Gaussian noise channel (AWGN). Since then, it has been shown that LDPC codes can come very close to capacity on many practical communication and recording channels. Therefore, LDPC codes have been considered as an alternative to turbo codes. Specifically, LDPC codes exhibit a better asymptotic performance than turbo codes, they are less affected by error floors, and offer a variety of tradeoffs between decoder complexity and performance. An advantage of LDPC codes is the low implementation complexity of the sum-product algorithm that is used to decode them. Simplified versions of the sum-product algorithm drive complexity lower with negligible loss in decoding performance as compared to full sum-product decoding.
In many magnetic recording applications such as hard-disk drives or tape systems, information is stored in binary form. In these applications, inner modulation codes concatenated with outer Reed-Solomon codes are employed to provide reliable extraction of the written information. Turbo and LDPC codes may push the areal density of magnetic recording systems to the limit for presently available magnetic components. It has been shown that, despite present sector-size constraints of hard-disk drives limiting the block length of a code and the high code-rate requirement, simple iterative decoding schemes can bring performance within approximately 1.5 dB of the theoretical limit. This represents a significant gain compared to existing systems. High-rate LDPC codes appear to have advantages over convolutional or turbo codes when used as outer codes in a magnetic recording system. For example, LDPC codes do not seem to suffer from error floors at error rates of 10−8. Furthermore, the sparseness of the parity-check matrix of LDPC codes results in decoding algorithms that are less complex compared to serially concatenated systems with convolutional outer codes. Also, no interleaver is needed between the LDPC encoder and the channel, because interleaving can be implicitly incorporated into the LDPC code. The potential gains of LDPC codes over the traditional Reed-Solomon codes for the magnetic recording channel have been presented in, T. Mittelholzer, A. Dholakia, and E. Eleftheriou “Reduced-Complexity Iterative Decoding of Low Density Parity Check Codes for Generalized Partial Response Channels,” IEEE Trans. Magn., 37(2), pp. 721-728, March 2001. In magnetic is storage systems LDPC codes are expected to push the areal density to its ultimate limit.
In many communication systems, including both wired and wireless transmission systems, there are strict limitations on transmit signal bandwidth. Such limitations impose a demand for signal modulation with a number of levels greater than two. Many conventional systems employ Trellis-coded modulation (TCM) in such applications. However, a problem associated with TCM is that it is unsuitable for iterative decoding. Therefore, farther improvements in signal quality at an acceptable complexity are difficult to achieve.
“A turbo TCM scheme with low decoding complexity,” Catena Netwoks Inc., Temporary Document BI-090, ITU-T Study Group 15, Question 4, Goa, India, 23-27 Oct. 2000, “Proposal of decision making for turbo coding and report of performance evaluation of proposed TTCM(PCCC) with R-S code and without R-S code,” Mitsubishi Electric Corp., Temporary Document BI-003, ITU-T Study Group 15, Goa, India, 23-27 Oct. 2000, and “Results of the requirements requested in the coding ad hoc report,” Vocal Technologies Inc., Temporary Document HC-073, ITU-T Study Group 15, Question 4, Huntsville, Canada, 31 Jul.-4 Aug. 2000, describe turbo-coding schemes for multilevel ADSL and VDSL transmission. These turbo-coding techniques involve encoding of the information bits by parallel concatenation of convolutional encoders in recursive systematic form and iterative decoding by one of several possible turbo-decoding techniques. “Block product turbo codes for G.dmt.bis and G.lite.bis,” Globespan Inc., Temporary Document BA-063, ITU-T Study Group 15, Question 4, Antwerp, Belgium, 19-23 Jun. 2000 describes the application of block product codes using component Bose-Chaudhuri-Hoequenghem (BCH) codes and their soft iterative decoding based on the Chase algorithm. These techniques offer some performance enhancements over Trellis coding at the expense of incurring additional complexity.
Application development relating to the alternative coding technique of LDPC codes, as described in R. G. Gallager, “Low-density parity-check codes,” IRE Trans. Info. Theogy, vol. IT-8 pp. 21-28 Jan. 1962, D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes, Electron. Lett., vol. 32, no. 18, pp. 1645-1646, Aug. 1996, D. J. C. MacKay. “Good error-correcting codes based on very sparse matrices,” IEEE Trans. on Inform. Theory, vol. 45, No. 2, pp. 399-431, Mar. 1999, and FOSSORIER, M. P. C., MIHALJEVIC. M., and IMAI, H.: “Reduced complexity iterative decoding of low density parity check codes based on belief propagation”, IEEE Trans. Commun., 1999, 47, (5), pp. 673-680, has to date focussed on applications requiring binary modulation such as wireless systems or digital magnetic recording. LDPC codes can also, however, be applied to multilevel transmission.
K. R. Narayanan and J. Li, “Bandwidth efficient low density parity check coding using multilevel coding and interative multistage decoding,” Proc. Int. Symp. on Turbo-Codes, Brest, France, pp. 165-168. September 2000 describes a multilevel coding technique based on binary LDPC block codes. This technique uses LDPC block codes for bit-interleaved modulation or for multilevel coding with iterative multi-stage decoding. For bit-interleaved LDPC modulation according to this technique, all the bits used to select a multilevel symbol are LDPC code bits. For multilevel coding, several LDPC block codes are used as component codes in a multilevel scheme. This technique has the drawback of requiring more than one LDPC encoder/decoder, leading to substantial implementation complexity especially for long codes and/or large constellation sizes.
“Low density parity check coded modulation for ADSL,” Aware Inc., Temporary Document BI-081, ITU-T Study Group 15, Question 4, Goa, India, 23-27 Oct. 2000 also describes a multilevel coding technique based on binary LDPC block codes. This technique is similar to TCM, except that LDPC coding is employed instead of convolutional coding. In particular, set partitioning follows the same principle as that used in TCM. This technique has the drawback of requiring an additional Bose-Chaudhuri-Hoeguenghem (BCH) code which adds to system complexity. Also, set partitioning, as required in TCM and similar schemes, leads to poor performance for soft-decision based decoding techniques.
Temporary Document RN-25, ITU Telecommunications Standardization Sector, Study Group 15, New Jersey, USA, 21-25 May 2001 describes a deterministic LDPC methodology and its applications to ADSL and ADSL Lite transmission. The methodology proposed therein requires a precomputation of the a generator matrix using, for example, Gaussian elimination. The encoding requires O(N2) operations.
Co-pending IBM patent application Ser. No. 10/045,810 describes a method for multilevel data communication comprising: dividing a set of information bits to be transmitted into a first group and a second group; encoding the first group to generate a block code; selecting a subset of symbols in a constellation of symbols in dependence on the block code according to a Gray-coded mapping function; selecting a symbol within the subset in dependence on the second group according to a Gray-coded mapping function; and, transmitting the selected symbol. This method offers superior performance in terms of achievable coding gains. The coding gains arise because block coding schemes can be decoded iteratively, thereby leading to substantial performance gains as compared to trellis-coded modulation. Particularly preferred embodiments of this method comprise multilevel encoding schemes based on LDPC codes or simple product codes that do not need interleaving and that can be decoded via the simple sum-product algorithm (SPA) or low-complexity derivatives thereof.
A disadavantage associated with LDPC codes is that they demand relatively high encoding complexity. When an LDPC code word is obtained by multiplying the information block with the generator matrix of the code, encoding requires O(N2) operations, where N is the length of the code. Such an encoding procedure is not “linear in time.” Furthermore, there is a preprocessing step needed to compute the generator matrix of the code from the specified LDPC parity-check matrix. The computation of the generator matrix involves Gaussian elimination, which requires O(N3) operations. Even though the preprocessing can be performed once for a particular LDPC check matrix and can be carried out off line, the computation cost can be prohibitive when decoding for applications requiring selection of one of a family of parity check matrices. This is the case, for example, in XDSL where the code is selected on a per connection basis. The topic of efficient encoding for LDPC codes has been addressed in L. Ping, W. K. Leung, and N. Phamdo, “Low density parity check codes with semi-random parity check matrix,” Electron. Letters, Vol. 35, No. 1, pp. 38-39, 7th Jan .1999; D. J. C. MacKay, S. T. Wilson, and M. C. Davey, “Comparison of constructions of irregular Gallager codes,” IEEE Trans. on Communications, Vol. 47, No. 10, pp. 1449-1454, October 1999; and, R. Richardson and R. L. Urbanke, “Efficient encoding of low-density parity-check codes.” IEEE Trans. on Information Theory, Vol. 47., No. 2, pp.638-656, February 2001.
In L. Ping, W. K. Leung, and N. Phamdo, “Low density parity check codes with semi-random parity check matrix,” Electron. Letters, Vol. 35, No. 1, pp. 38-39, 7th Jan. 1999, the parity-check matrix of the LDPC code is “semi-random” in the sense that it includes a deterministic and a random part. The deterministic part is in a band-diagonal or “zigzag” form to allow efficient encoding. The rest of the parity-check matrix is created randomly by avoiding 4-cycles. In D. J. C. MacKay, S. T. Wilson, and M. C. Davey, “Comparison of constructions of irregular Gallager codes,” IEEE Trans. on Communications, Vol. 47, No. 10, pp. 1449-1454, October 1999 and R. Richardson and R. L. Urbanke, “Efficient encoding of low-density parity-check codes,” IEEE Trans. on Information Theory, Vol. 47., No. 2, pp. 638-656, February 2001, the parity-check matrix is again generated by a random construction and a triangular or “approximate triangular” form is imposed to allow efficient encoding. These constructions each lead to linear-time encodable LDPC codes. However, they have a number of drawbacks, including:    (a) Randomly constructed parity-check codes cannot be specified via a small number of parameters. In other words, all the positions of the nonzero elements of the parity-check matrix must be individually given;    (b) preprocessing is sometimes required to bring the parity-check matrix into triangular or approximate triangular form; and,    (c) the codes obtained result in loss in performance as compared with randomly constructed LDPC codes.
In would be desirable to provide parity-check matrices that lead to LDPC codes having linear-time encoding complexity. It would also be desirable to provide parity-check matrices that are fully deterministic and can be specified via a small number of parameters. It would also be desirable to provide parity-check matrices that require a minimum amount of, or no, preprocessing.